# https://leetcode.cn/problems/count-the-number-of-good-nodes/description/?envType=daily-question&envId=2024-11-14

class Solution:
    def countGoodNodes(self, edges: list[list[int]]) -> int:
        adjacencyList: list[list[int]] = [[] for _ in range(len(edges) + 1)]
        for i, j in edges:
            adjacencyList[i].append(j)
            adjacencyList[j].append(i)
        res = [0]

        # 计算
        def dfs(root: int, father: int) -> int:
            sonTreeNode = []
            for nextNode in adjacencyList[root]:
                if nextNode == father:
                    continue
                sonTreeNode.append(dfs(nextNode, root))
            for index in range(1, len(sonTreeNode)):
                if sonTreeNode[index] != sonTreeNode[index-1]:
                    break
            else:
                res[0] += 1
            return sum(sonTreeNode) + len(adjacencyList[root]) - 1 if len(sonTreeNode) > 0 else 0

        dfs(0, -1)
        return res[0]
